/*
1944. 队列中可以看到的人数
https://leetcode.cn/problems/number-of-visible-people-in-a-queue/description/
困难 2024/12/04
*/

class Solution {
public:
    vector<int> canSeePersonsCount(vector<int>& heights) {
        int n=heights.size();
        vector<int>arr(n,0);
        stack<int>st;
        //从队伍末尾开始，维护一个单调栈，从栈底到栈顶，身高严格递减
        for(int i=n-1;i>=0;i--)
        {
            while(!st.empty()&&st.top()<heights[i])
            {
                st.pop();
                arr[i]+=1;
            }
            if (!st.empty())//不为空说明栈内存在元素比heights[i]大
                arr[i] += 1;
            st.push(heights[i]);
        }
        return arr;
    }
};